Cancelling in Linear Congruences

This note deals with two circumstances in which terms may be divided through in linear congruences without effecting the set of solutions.

Theorem

The linear congruences $ax = b \pmod m$ and $cax = cb \pmod{cm}$ have the same solution set in $x$ given that $c \neq 0$.

Proof

$x$ is a solution to the congruence $ax = b \pmod m$ if and only if there exists a $y$ such that:

\[ ax + my = b.\]

It is easy to then see that multiplying through by $c \neq 0$ has no effect on the solution set.

Theorem

The linear congruences $ax = b \pmod m$ and $cax = cb \pmod m$ have the same solution set if $\gcd(c, m) = 1$.

Proof

We will show this be showing two implications. First, if $x$ is a solution to the equation $ax = b \pmod m$, it is necessarily a solution to $cax = cb \pmod m$.

In the opposite direction, we consider the following equivalent conditions:

\[\begin{align*} cax = cb \pmod m &\iff m \mid cax - cb \\ &\iff m \mid c(ax - b) \\ &\implies m \mid ax - b \tag{Since $\gcd(m, c) = 1$} \\ &\iff ax = b \pmod m \\ \end{align*}\]

This result can also be proven by using the existence of an inverse for $c$ given the coprimality condition.